public class Main {
    /*
        * 迷宫大阵
        * 假设有一个迷宫，里面有障碍物，迷宫用二维矩阵表示，标记为0的地方表示可以通过，标记为1的地方表示障碍物，
          不能通过。现在给一个迷宫出口，让你判断是否可以从入口进来之后，走出迷宫，每次可以向任意方向走。
        * 队---先进先出
        * 队 中 保存的是广度优先搜索 最外面的一层位置
        * 广度优先搜索  就像是一滴水滴在一张纸上，然后水向四面八方（或者向某些方向）扩散，最后阴湿这张纸，找到要搜索的位置
        *
        *
        *
        * */
    static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return x == pair.x &&
                    y == pair.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public static boolean BFS(int[][] graph, int startX, int startY, int endX, int endY) {
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(startX, startY));
        int row = graph.length;
        int col = graph[0].length;
        //标记数组
        int[][] books = new int[row][col];
        //移动数组
        int[][] nextP = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            if (pair.x == endX && pair.y == endY && graph[pair.x][pair.y] != 1) {
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int newX = pair.x + nextP[i][0];
                int newY = pair.y + nextP[i][1];
                if (newX >= row || newX < 0 || newY >= col || newY < 0 || graph[newX][newY] == 1 || books[newX][newY] == 1) {
                    continue;
                }
                books[newX][newY] = 1;
                queue.offer(new Pair(newX, newY));
            }
        }
        return false;
    }
}